Skip to main content

계수 정렬

계수 정렬(Counting Sort)​

  • 계수 정렬은 Counting Sort로 요소의 값들끼리 서로 비교하지 않고 정렬하는 알고리즘
  • 배열 내 최대 값 + 1 만큼의 길이 배열이 필요 => 메모리 낭비될 수 있음
  • 최대값과 최소값을 알아야 쓸 수 있음
  • 시간 복잡도는 O(n+k)O_{(n+k)}
    • 배열counts 생성 O(k)O_{(k)}
    • 배열counts에 카운팅 값 입력 O(n)O_{(n)}
    • 배열counts에 누적값 업데이트 O(k)O_{(k)}
    • 정렬 결과 배열sorted 채우기 O(n)O_{(n)}

선택 정렬 구현​

계수 정렬 애니메이션 에 들어가서 애니메이션을 보시면 이해하기 편합니다

void Counting_Sort() {
    int MAX = 5;
    int[] nums = { 0, 1, 5, 4, 2, 3, 2, 4, 5, 3, 2, 1, 2, 0, 0 };
    int len = nums.length;
    int[] counts = new int[MAX + 1];
    int[] sorted = new int[len];

    for (int i = 0; i < len; i++) {
        counts[nums[i]]++;
    }

    for (int i = 0; i < MAX+1; i++) {
        System.out.print(counts[i]+" ");
    }
    System.out.println();
        
    for (int i = 1; i <= MAX; i++) {
        counts[i] += counts[i - 1];
    }

    for (int i = 0; i < MAX+1; i++) {
        System.out.print(counts[i]+" ");
    }
    System.out.println();
        
    for (int i = 0; i < len; i++) {
        sorted[--counts[nums[i]]] = nums[i];
    }

    for (int i = 0; i < len; i++) {
        System.out.print(sorted[i]+" ");
    }
    System.out.println();
}

결과 :

선택정렬 시간복잡도

  1. 주어진 nums 배열의 앞쪽부터 하나씩 counts 배열에 집어넣는다.
  2. counts 배열을 누적 합으로 변경시켜 준다.
  3. nums 배열의 맨 뒤의 숫자부터 차례로 sorted 배열에 집어넣는다.(sorted 배열은 1부터 시작하는 배열)

출력을 하게 되면 정렬된 결과가 나오게 된다.

tip

사용하기 좋은 예 : 데이터의 범위는 상대적으로 좁은데 비해 데이터의 갯수가 많은 경우

ex) 1~ 1,000,000의 범위를 가지는 수가 1억개 있는 경우

계수 정렬의 장단점​

장점​

  1. 매우 빠른시간에 정렬할 수 있다.
  2. 안정 정렬이다.

단점​

  1. 배열의 인덱스를 이용하기 때문에 정해진 범위에 한정하여 정렬 가능

  2. 가장 큰수에 따라서 메모리 잡는 부분이 달라진다.

나올 수 있는 면접 질문​

  • 계수 정렬이란 무엇일까?
  • 계수 정렬을 사용할 수 있는 조건은?
  • 계수 정렬을 언제 사용하는 것이 좋을까?

참고 url​

계수 정렬 애니메이션

멍멍멍 - 계수 정렬

wordbe - 계수 정렬 시간복잡도

기여자​


HelloNaks
📦